import numpy as np

array = np.random.randint(low=1, high=1000, size=10)

print(array)

# 先排序，在查找
array.sort()
print(array)


def fibonacci_search(a: list, target: int) -> object:
    n = len(a)
    f = fibonacci(2 * n)
    k = 0
    while n > f[k] - 1:
        k += 1
    aux = append_array(a, f[k] - 1)
    return sort(0, len(a) - 1, a, aux, f, k, target)


def sort(low: int, high: int, a: list, aux: list, f: list, k: int, target: int) -> object:
    while low <= high:
        middle = low + f[k - 1] - 1
        if target < aux[middle]:
            high = middle - 1
            k = k - 1
        elif target > aux[middle]:
            low = middle + 1
            k = k - 2
        else:
            if middle < len(a):
                return middle + 1
            else:
                return len(a)
    return -1


def fibonacci(size: int) -> object:
    f = [None] * size
    for i, x in enumerate(f):
        f[i] = f[i - 1] + f[i - 2] if i >= 2 else 1
    return f


def append_array(a: list, size: int) -> object:
    n = len(a)
    aux = [None] * size
    for i, x in enumerate(aux):
        aux[i] = a[i] if i < n else a[n - 1]
    return aux

value = array[np.random.randint(low=0, high=10, size=1)]

print(value)

print(fibonacci_search(array, value))
